Uber社で使われている地理的インデックスシステム(H3)をPostgreSQLで利用できるh3-pg拡張機能を試してみました。
初めに
先日Amazon RDS for PostgreSQL 16のbeta3がリリースされました。
上記リページには含まれていなかったのですがリリースノート(英語版)側を確認したところh3-pgというなにやら見かけない拡張機能の追加情報が含まれておりました。
調べてみたところUber社が開発しており現在オープンソースとなっているH3と呼ばれる地理的インデックスシステムをPostgreSQLの拡張機能として利用できるようにしたもののようです。
PostgreSQLだけではなく現時点ではC,Python,Java,JavaScript向けにAPIが提供されているためこちらを利用することも可能です。
私自身地理情報システム(GIS)に関してはあまり詳しくないのですが気になるので触りだけでもやってみようと思います。
RDS for PostgreSQL 16 beta 3ではまだ使えない？
今回せっかくRDS for PostgreSQLで対応しているとのことなので試してみようと思いましたがどうやらまだ使えない？（何か設置すればいける？）感じでした。
拡張機能としては実際に存在しているようでしたが有効化してみようとすると共有ライブラリ不足でエラーとなりました。
$ SELECT * FROM pg_available_extensions WHERE name LIKE '%h3%';
name | default_version | installed_version | comment
------------+-----------------+-------------------+----------------------------
h3_postgis | 4.1.3 | | H3 PostGIS integration
h3 | 4.1.3 | | H3 bindings for PostgreSQL
(2 rows)
postgres=> create extension h3;
ERROR: could not load library "/rdsdbbin/postgres-16.20230807.R1/lib/h3.so": libpq.so.5: cannot open shared object file: No such file or directory
いつものshared_preload_librariesと思ったのですがこちらの場合はそもそも違うエラーなので何か別の原因かと思いますが、beta版というところもあるので不完全な関係か自分の設定のところか切り分けができていません。
$ CREATE EXTENSION plrust; ERROR: plrust must be loaded via shared_preload_libraries
betaが抜けた頃には対応するかと思うのでとりあえず今回は一旦置いて別の環境で試してみようと覆います。
RDS for PostgreSQLでも対応していることを確認しました(2023/08/25追記)
本日公開されたマイナーバージョンでh3-pgが正式対応していました。
ドキュメントの方では英語版を含めまだ16-beta3以外に対応している拡張機能として記載がなかったのですが、15.4では実行まで動作を確認しております。
% psql -h xxxxx.xxxxx.ap-northeast-1.rds.amazonaws.com -U postgres
...
SELECT version();
version
---------------------------------------------------------------------------------------------------------
PostgreSQL 15.4 on x86_64-pc-linux-gnu, compiled by gcc (GCC) 7.3.1 20180712 (Red Hat 7.3.1-12), 64-bit
(1 row)
postgres=> create extension h3;
CREATE EXTENSION
postgres=> SELECT h3_cell_to_lat_lng('872f5aadeffffff');
h3_cell_to_lat_lng
---------------------------------------
(139.7586016409392,35.66916813197301)
(1 row)
-- h3_postgisがないとできないは未確認
postgres=> create extension h3_postgis cascade;
NOTICE: installing required extension "postgis"
NOTICE: installing required extension "postgis_raster"
CREATE EXTENSION
H3とは
どういったものかは以下のUber社のブログにて語られています。
当記事における記載はこちらの記事を読んだ上での自分の理解を一部抜粋したものとなり正確なものではない可能性があるため詳細はUber社のブログをご参照ください。
本当にざっくり概念としては地球上を正六面体のグリッドで埋めそのグリッドを活用することで測量に関する分析を平滑化するための手法のようです。
目的としては前述の通りUberの配送の最適化のためとなりますが、これを行うために地球上を正二十面体として取り扱い、さらにそれをそのまま展開するだけではなくその上にグリッドをを配置するグローバルで離散的な測量システムのようです。
正十二面体での各面はさらに分割され正六角形のグリッドが配置されることで構築されていますが(跨ぎ有)。
ただし完全にこれでマッピングすることは無理であったため正二十面体の各面の頂点部分には五角形のグリッドを含めることで対応しているようです。
(五角形グリッドについては作業影響が少なくなるように水面上に配置しているとのこと)
六角形という形を採用した理由としては、グリッドの中心から隣接するグリッドの中心に対しての距離を計算する場合に三角形や四角形では１つにならないが六角形の場合はこれが1つになるというメリットがあり選択がされています。
例えば正方形のグリッドの場合、隣接するグリッドの中央に対する距離の計算には以下の２種類の距離が必要であり分析に対して必要な処理がその分複雑となってしまいます。
- 正方形の一片の距離
- 面で接する隣接する正方形グリッドへの距離
- 正方形の対角線の距離
- 点(角)で隣接する正方形のグリッドへの距離)
正六角形の場合隣接するグリッドとは全て面で接しているため、隣接するグリッドへの距離はどの方向であっても常に一意となるため解析の実行時の平滑化のコストを大きく下げることができます。
※ 部分的に補助線を入れてるので少しわかりづらいですが全て辺で接してるので一辺の√3倍が2つの中心の距離です
またH3では正六角形の中にはさらに7つの正六角形が、さらにその中にもという形で階層化されており、１６段階の解像度が用意されています。
ただし１つ上のサイズ(大きい側)の六角形を綺麗に7つの正六角形に分割できることは不可能なため、１段階細かな正六角形グリッド群は元のグリッドと綺麗に一致しているわけではなく多少のはみ出し等(歪み)はあるとのことです。
グリッドは一定の形にマッピングされいるためグリッド単体による分割が必ずしもその地域の事情とマッチしているとは限りません。
なので実際にはこのシステムはクラスタリング等の分析を効率的に行うための要素とするためのもののようです。
使ってみる
Amazon Linux 2023(以降AL2023)上にpostgreSQLサーバを立ち上げて試してみます
インストール
バージョンの依存等々の関係でAL2023デフォルトのリポジトリにあるPostgreSQL 15を使うのは手順がややこしくなりそうだったので、fedora 36のリポジトリからPostgreSQL 14やpostgisをインストールする方法をとっています。
$ yum install -y cmake gcc pip
$ yum install -y postgresql{,-server,-server-devel} postgis --enablerepo=fedora36
# initdbだけpostgresユーザで実行
$ initdb
$ service postgresql start
# h3の依存の関係でpostgisが必要なので有効化する
$ psql -U postgres -c "CREATE EXTENSION postgis"
$ psql -U postgres -c "CREATE EXTENSION postgis_raster"
$ pip install pgxnclient
$ pgxn install h3
$ pgxn load h3 -U postgres
fedora36は以前fedora34で試したのと同じような感じでfedora 36の標準リポジトリを参照できるように設定しています。
これで導入は完了です。
実行
docs/api.mdの情報をもとに幾つか処理を実行してみます。
h3_lat_lng_to_cell()に対して地点情報(緯度経度)と解像度を指定することでそのセル(グリッド)を取得できるようなのでこれでクラスメソッド本社のある日比谷フォートタワーの緯度経度を入れて取得してみましょう。
Google Map等からコピペすると(緯度, 経度)で取得されますがPOINTの指定は(経度(x座標), 緯度(y座標))なので注意しましょう。
-- 解像度は16段階(0~15)あるので中間ほどの7を指定してみる
$ SELECT h3_lat_lng_to_cell(POINT('139.75297111216622, 35.670172852452204'), 7);
h3_lat_lng_to_cell
--------------------
872f5aadeffffff
(1 row)
返却値はH3Indexというものでドキュメントを読む限りこれが各グリッドの情報となるようです。
h3_cell_to_lat_lng()にh3index情報を指定することでセルの中心、h3_cell_to_boundary()にh3index情報を指定することでそのセルのエッジ（頂点情報)が得られます。
$ SELECT h3_cell_to_lat_lng('872f5aadeffffff');
h3_cell_to_lat_lng
---------------------------------------
(139.7586016409392,35.66916813197301)
(1 row)
$ SELECT h3_cell_to_boundary('872f5aadeffffff');
h3_cell_to_boundary
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
------------------------------------------------------
((139.77249490111734,35.66585631052455),(139.7685388815989,35.67813460513031),(139.75464385114776,35.68144488899651),(139.74470957311203,35.672477798907686),(139.74866802714678,35.660
20210153104),(139.76255832579878,35.656890897112085))
(1 row)
上記のポイントを地図上に書き起こしてみます。
赤マーカーが日比谷フォートタワー、青マーカーがセルの中心、緑マーカーがエッジです。
大阪オフィスまでの距離を見てみましょう
-- 大阪オフィスのh3index情報を取得
$ SELECT h3_lat_lng_to_cell(POINT('135.4964737597688, 34.69036403934684'), 7);
h3_lat_lng_to_cell
--------------------
872e61051ffffff
(1 row)
-- h3_grid_distance()でs3index間の距離を取ることができる。単位はセル数
$ SELECT h3_grid_distance('872f5aadeffffff','872e61051ffffff');
h3_grid_distance
------------------
188
(1 row)
-- h3_get_hexagon_edge_length_avg()でその解像度におけるグリッドの１辺の大体の長さが取れます
$ SELECT h3_get_hexagon_edge_length_avg(7);
h3_get_hexagon_edge_length_avg
--------------------------------
1.220629759
(1 row)
間に188個のグリッドがあるので距離的にはグリッド189個分一辺あたりが約1.2km、先に記載したとおり隣接2つの六角形の中心距離は一辺の√3倍ですので、
２点間の距離は大体399.36km、Google Mapで見る限りも直線距離は概ね400kmですのでグリッドによる丸めや小数点等計算等を考えれば大体そんなものでしょう。
実際には綺麗に直線を移動をするわけではないので中間点をいくつか置きながら距離を測るのかなという感じです。
終わりに
今回はPostgreSQL経由でH3というものがどういうものであるかを簡単に確認してみました。
GIS周りに疎いところはあるので実際の活用やメリットについて個人的に具体的な活用はイメージがしづらいところではあるのですが、正確な算出はともかく大枠的な推量としてこれで十分できそうですし、計算としても仕組みがシンプルかつそれが一定のものであるので取り扱いやすいでしょう。
PostgreSQLの拡張機能だけではなく幾つかのプログラミング言語で利用可能なインターフェースも提供されていますので、活用できるのではというアイデアがある方はぜひ一度触ってみてはいかがでしょうか。
![[アップデート] Amazon Aurora のモニタリング機能に「CloudWatch Database Insights」が登場しました](https://images.ctfassets.net/ct0aopd36mqt/3nibOl2sZ0LKJueI0FHFi5/14de7bd294f7916a28b789105c60d450/reinvent-2024-newservice-jp.jpg)
